

#include "stl_list.h"

#define ListNode_pool_size  256   // ListNode 链表池的大小，一个节点的大小是sizeof(ListNode) = 8。

ListNode ListNode_pool[ListNode_pool_size];
int ListNode_remain_number = ListNode_pool_size;
int ListNode_pool_first1 = 0;		   // 第一个表是满的，头节点从0开始，这个是未分配过的节点池
ListNode* ListNode_pool_first2 = NULL; // 第二个表是空表，这个是回收的节点的头节点。

#if(0)

ListNode* ListNode_allocate()
{
	ListNode* p;
	if (ListNode_pool_first2 == NULL) {
		if (ListNode_pool_first1 == ListNode_pool_size) {
			printfs("\r\n  ListNode_allocate faild \r\n ");
			return NULL; // 分配失败
		}
		p = ListNode_pool + ListNode_pool_first1;
		ListNode_pool_first1++;
	}
	else {
		p = ListNode_pool_first2;
		ListNode_pool_first2 = ListNode_pool_first2->next;
	}
	ListNode_remain_number--;
	p->datap = NULL;
	p->next = NULL;
	return p;
}

void ListNode_deallocate(ListNode* p)
{
	if (p >= ListNode_pool && p < &ListNode_pool[ListNode_pool_size]) {   //使用头插法将回收的链表节点放到ListNode_pool_first2
		p->next = ListNode_pool_first2;
		ListNode_pool_first2 = p;
		ListNode_remain_number++;
	}
}

#else

// 判断节点池是否正常：方法：判断空余节点链表是否完整。
bool check_node_pool()
{
	int k = 1;
	ListNode* p = ListNode_pool_first2;   //printfs(" %d ", p);
	while (p->next != ListNode_pool_first2)
	{
		p = p->next;  //	printfs(" %d ", p);
		k++;
	}
	//printfs(" \r\n -----    %d  %d --------  \r\n  ", k,ListNode_remain_number);
	if (k == ListNode_remain_number) {
		return true;
	}
	return false;


	for (int i = 0; i < ListNode_remain_number; i++) {
		p = p->next;
	}

	if (p == ListNode_pool_first2) return true;
	return false;
}

bool is_init = false;
ListNode* ListNode_allocate()
{
	if (is_init == false) {
		is_init = true;
		ListNode_pool_first2 = ListNode_pool;
		for (int i = 1; i < ListNode_pool_size; i++) {
			ListNode_pool[i - 1].next = &ListNode_pool[i];
		}
		ListNode_pool[ListNode_pool_size - 1].next = ListNode_pool;
		ListNode_remain_number = ListNode_pool_size;
		printfs(" \r\n check pool %d  \r\n  ", check_node_pool());
	}
	ListNode* p = NULL;

	if (ListNode_pool_first2->next != ListNode_pool_first2) {
		p = ListNode_pool_first2->next;
		ListNode_pool_first2->next = ListNode_pool_first2->next->next;
		ListNode_remain_number--;

		printfs(" \r\n check pool allocate %d  \r\n  ", check_node_pool());

	}
	return p;
}

void ListNode_deallocate(ListNode* p)
{
	if (p >= ListNode_pool && p < &ListNode_pool[ListNode_pool_size]) 
	{   //使用头插法将回收的链表节点放到ListNode_pool_first2

		printfs(" \r\n     before      check pool deallocate %d   === %d  ---  \r\n  ", check_node_pool(), p - ListNode_pool);
		p->next = ListNode_pool_first2->next;
		ListNode_pool_first2->next = p;
		ListNode_remain_number++;
		printfs(" \r\n check pool deallocate %d   === %d  ---  \r\n  ", check_node_pool(), p - ListNode_pool);
	}

	
}

#endif

/// <summary>
/// 返回剩余可分配节点数量
/// </summary>
/// <returns></returns>
int ListNode_remain()
{
	return ListNode_remain_number;
}


/// <summary>
/// 初始化链表
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="c">链表节点的比较函数。在有序插入的时候要用到。这里的 Datapointer 是 ListNode* </param>
void list_init(List* list, int (*c)(Datapointer, Datapointer))
{
	
	list->count = 0;
	list->match = c;

	list->tail = NULL;
}

/// <summary>
/// 销毁链表。
/// </summary>
/// <param name="list">链表结构体</param>
void list_destroy(List* list)
{
	if (list->count <= 0) {
		list->count = 0;
		list->tail = NULL;
		return;
	}


	ListNode* p0 = list->tail;
	ListNode* p1;
	int count = list->count;
	for (int i = 0; i < count; i++) {
		p1 = p0->next;
		ListNode_deallocate(p0);
		p0 = p1;
	}

	list->count = 0;
	list->tail = NULL;
}

/// <summary>
/// 链表头节点的数据
/// </summary>
/// <param name="list">链表</param>
/// <returns>数据指针 </returns>
Datapointer list_head(List* list)
{
	if (list->count == 0)return NULL;
	else return list->tail->next->datap;
}

/// <summary>
/// 链表尾节点的数据
/// </summary>
/// <param name="list">链表</param>
/// <returns>数据指针 </returns>
Datapointer list_tail(List* list)
{
	if (list->count == 0)return NULL;
	else return list->tail->datap;
}

/// <summary>
/// 在链表尾部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="datap">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool list_push_back(List* list, Datapointer datap)
{
	ListNode* n = ListNode_allocate();
	if (n == NULL)return false;
	if (list->count == 0)list->tail = n; // 如果是空表，需要先给tail赋值
	n->datap = datap;
	n->next = list->tail->next;
	list->tail->next = n;
	list->tail = n;
	list->count++;
	return true;
}

/// <summary>
/// 在链表头部插入一个元素。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="datap">新插入的节点</param>
/// <returns>是否操作成功</returns>
bool list_push_front(List* list, Datapointer datap)
{
	ListNode* n = ListNode_allocate();
	if (n == NULL)return false;
	if (list->count == 0) { list->tail = n; }// 如果是空表，需要先给tail赋值
	n->datap = datap;
	n->next = list->tail->next;
	list->tail->next = n;
	list->count++;
	return true;
}

/// <summary>
/// 在链表头部弹出一个数据
/// </summary>
/// <param name="list">链表结构体</param>
/// <returns>是否操作成功</returns>
Datapointer list_pop_front(List* list)
{
	if (list->count == 0)return NULL;
	Datapointer dp = list->tail->next->datap;
	ListNode* h = list->tail->next;
	list->tail->next = h->next;  // 链表删除头节点
	ListNode_deallocate(h);
	list->count--;
	if (list->count == 0) list->tail = NULL;
	return dp;
}

/// <summary>
/// 按序插入节点。按照从小到大的顺序插入。如果所有元素都是按序插入的，整个链表就是有序的。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="datap">新插入的节点</param>
bool list_ins_orderly(List* list, Datapointer datap)
{
	if (datap == NULL) {
		return false;
	}
	else
	{
		if (list->count == 0 || list->match(list_tail(list), datap) == -1) { 
			//空链表 或 比尾节点大，直接插最后
			return list_push_back(list, datap);
		}
		if (list->match(list_head(list), datap) == 1) { 
			// 比头节点小，直接插最前
			return list_push_front(list, datap);
		}
		else
		{
			ListNode* precursor = list->tail->next;
			ListNode* cursor = precursor->next;  // 当前cursor 是头节点。
			for (int i = 0; i < list->count - 2; i++) {  // 不需要再比较头节点和尾节点了。
				if (list->match(cursor->datap, datap) != -1) {
					return list_ins_next(list, precursor, datap);
				}
				precursor = cursor;
				cursor = cursor->next;
			}
			return list_ins_next(list, precursor, datap);  // 如果到这里，就是插入到尾节点的前一个节点了。

		}
	}
}


/// <summary>
/// 在 node 后面插入一个新元素，如果node是尾节点，则新插入的节点会成为尾节点
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">定位的节点</param>
/// <param name="datap">新插入的节点</param>
/// <returns>是否插入成功，如果node是合法的节点，是可以成功插入的</returns>
bool list_ins_next(List* list, ListNode* node, Datapointer datap)
{
	if (list->count == 0)return list_push_front(list, datap);
	ListNode* n = ListNode_allocate();
	if (n == NULL)return false;
	if (node == list->tail)list->tail = n; // 检查是否需要刷新尾节点
	n->datap = datap;
	n->next = node->next;
	node->next = n;
	list->count++;
	return true;
}

/// <summary>
/// 在 node 前面插入一个新元素.
/// 等效于在node后面插一个元素，然后调换node和node->next 的值
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">定位的节点</param>
/// <param name="datap">新插入的节点的数据</param>
/// <returns>是否插入成功，如果node是合法的节点，是可以成功插入的</returns>
bool list_ins_prev(List* list, ListNode* node, Datapointer datap)
{

	if (list->count == 0)return list_push_front(list, datap);
	ListNode* n = ListNode_allocate();
	if (n == NULL)return false;
	if (node == list->tail)list->tail = n; // 检查是否需要刷新尾节点
	n->datap = node->datap;
	n->next = node->next;
	node->datap = datap;
	node->next = n;
	list->count++;
	return true;
}

/// <summary>
/// 在链表 中移除 node 元素，为了使操作时间复杂度在O(1),采用下面的方法：
/// 将node下一个节点的值赋值给node，再删除下一个节点。
/// 注意：这里有个风险：如果node是尾节点，那么删除之后，原来的头节点会变成尾节点。
/// 不过，链表的大部分用途不关心节点顺序。如果需要关心节点顺序，就用list_remove_next
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">移除的节点</param>
/// <returns>是否操作成功。如果node是合法的节点，是可以操作成功的</returns>
bool list_remove(List* list, ListNode* node)
{
	//if (node->datap == 0xFFFFFFFF) {
	//	printfs("\r\n  delete pool node  !!! \r\n");
	//	return false;
	//}
	if (list->count <= 0 || node == NULL) {
		list->count = 0;
		list->tail = NULL;
		return false;
	}
	ListNode* n = node->next;
	node->datap = n->datap;
	if (n == list->tail) {
		list->tail = node;  // 检查是否需要跟新尾节点
	}
	node->next = n->next;  
	ListNode_deallocate(n);
	list->count--;
	if (list->count == 0) list->tail = NULL;
	return true;
}

/// <summary>
/// 在链表 中移除 node 下一个节点。
/// 如果下一个节点是尾节点，node会成为新的尾节点。
/// 如果node是尾节点，会移除头节点。
/// </summary>
/// <param name="list">链表结构体</param>
/// <param name="node">移除的节点</param>
/// <returns>是否操作成功。如果node是合法的节点，是可以操作成功的</returns>
bool list_remove_next(List* list, ListNode* node)
{
	if (list->count <= 0 || node == NULL) {
		list->count = 0;
		list->tail = NULL;
		return false;
	}
	ListNode* n = node->next;
	if (n == list->tail)list->tail = node;  // 检查是否需要跟新尾节点
	node->next = n->next;  
	ListNode_deallocate(n);
	list->count--;
	if (list->count == 0) list->tail = NULL;
	return true;
}


// 测试list



int match(Datapointer key1, Datapointer key2)  //key1>key2返回1，key1<key2返回-1,key1=key2返回0.
{
	if (*(int*)key1 > *(int*)key2)return 1;
	else if (*(int*)key1 < *(int*)key2)return -1;
	else return 0;
}

void print_int_list(List list)
{
	ListNode* list_cursor;
	printfs("  positive order: ");
	if (list.count > 0) {
		printfs("head %d, ", *(int*)list_head(&list));
		printfs("tail %d, || ", *(int*)list_tail(&list));;
	}
	list_cursor = list.tail->next;
	for (int i = 0; i < list.count; i++) {
		printfs(" %d, ", *(int*)list_cursor->datap);
		list_cursor = list_cursor->next;
	}
	printfs("  \r\n");

}

void test_list()
{
	List list;
	list_init(&list, match);
	//
	printfs(" inta[] =  5,4,1,2,3  \r\n");
	int inta[5] = { 5,4,1,2,3 };


	printfs("list.tail  list_ins_next \r\n");
	for (int i = 0; i < 5; i++) {
		list_ins_next(&list, list.tail, &(inta[i]));
		print_int_list(list);
	}
	print_int_list(list);

	printfs("list.tail  list_remove_next \r\n");
	for (int i = 0; i < 5; i++) {
		list_remove(&list, list.tail);
		print_int_list(list);
	}

	printfs("list.tail   list_ins_prev \r\n");
	for (int i = 0; i < 5; i++) {
		list_ins_prev(&list, list.tail, &(inta[i]));
		print_int_list(list);
	}
	print_int_list(list);


	printfs("list.tail  list_remove \r\n");
	for (int i = 0; i < 5; i++) {
		list_remove_next(&list, list.tail);
		print_int_list(list);
	}

	printfs("list_push_front \r\n");
	for (int i = 0; i < 5; i++) {
		list_push_front(&list, &(inta[i]));
	}
	print_int_list(list);



	list_destroy(&list);
	printfs("list_push_back \r\n");
	for (int i = 0; i < 5; i++) {
		list_push_back(&list, &(inta[i]));
	}
	print_int_list(list);

	printfs("list_pop_front \r\n");
	for (int i = 0; i < 5; i++) {
		list_pop_front(&list);
		print_int_list(list);
	}
	list_destroy(&list);

	//测试排序，按序插入。
	printfs("test list_ins_orderly \r\n");
	int intb[5] = { 5,4,1,8,3 };
	for (int i = 0; i < 5; i++) {
		list_ins_orderly(&list, &(intb[i]));
	}
	print_int_list(list);


	printfs(" test finish  \r\n ");

}












